class Solution(object):
    def lastRemaining(self, n):
        """
        :type n: int
        :rtype: int
        """
        stack = []
        index = 0
        while n > 1:
            stack.append([n, index % 2])
            n = n // 2
            index += 1
        stack.reverse()
        def search(s, val):
            if s[0] % 2 == 1:
                return 2 * val + 1
            else:
                if not s[1]:
                    return 2 * val + 1
                else:
                    return 2 * val
        val = 0
        for i in range(len(stack)):
            val = search(stack[i], val)
        return val + 1


data = Solution()
n = 9
print(data.lastRemaining(n))